package com.gy.algorithm.carl.strexa;


import java.util.Arrays;

/**
 * @BelongsProject: javabase
 * @BelongsPackage: com.gy.algorithm.carl
 * @Author: gy
 * @Date: 2024/10/22 11:30
 * @Description:
 */
public class StrStr28 {

    public static void main(String[] args) {
        System.out.println(strStr("aabaaabaaac","aabaaac"));

//        System.out.println(Arrays.toString(getNext("aabaaf")));
    }

    /***
     *
     * 整体流程：
     * 初始化
     * 处理前后缀不相同的情况
     * 处理前后缀相同的情况
     *
     * @author: gy
     * @date: 2024/10/23 17:34
     * @description:
     * @Param needle:  
     * @return: int[]
     */
    public static int[] getNext(String needle){

        char[] nextArr = needle.toCharArray();
        int len = nextArr.length;

        // 初始化
        int[] res = new int[len];
        // 单个字母无前缀后缀
        res[0] = 0;

        // j：前缀末尾 i：后缀末尾
        int j = 0;
        for (int i = 1; i < len; i++) {
            // 处理前后缀不相同的情况【遇见冲突 看前一位 】
            while (j > 0 && nextArr[i] != nextArr[j]) j = res[j-1];
            // 处理前后缀相同的情况【j加一】
            if(nextArr[i] == nextArr[j]) j++;
            // 更新next数组
            res[i] = j;
        }
        return res;
    }

    // end
    public static int strStr(String haystack, String needle) {

        if(needle.length() > haystack.length()) return -1;

        // 获得next数组
        int[] next = getNext(needle);

        int left = 0;
        int right = 0;

        char[] originalArr = haystack.toCharArray();
        char[] needArr = needle.toCharArray();
        int needLen = needArr.length;

        for (int i = 0; i < originalArr.length; i++) {
            while (left < originalArr.length && right < needLen && originalArr[left] == needArr[right]){
                left++;
                right++;
                // 匹配完成
                if(right == needLen){
                    return i;
                }
            }
            // 需要跳到模式串
            if(right > 0){
                right = next[right - 1];
                left = i + right + 1;
            }else{
                right = 0;
                left = i + 1;
            }

        }

        return -1;
    }

    // write
    public static int strStr1(String haystack, String needle) {

        int left = 0;
        int right = 0;

        char[] originalArr = haystack.toCharArray();
        char[] needArr = needle.toCharArray();
        int needLen = needArr.length;

        for (int i = 0; i < originalArr.length; i++) {
            while (left < originalArr.length && right < needLen && originalArr[left] == needArr[right]){
                left++;
                right++;
                // 匹配完成
                if(right == needLen){
                    return i;
                }
            }
            left = i + 1;
            right = 0;
        }

        return -1;
    }
}
